IT265 DESIGN AND ANALYSIS OF ALGORITHMS

Title of the unit Minimum number of hours
1 Basics of Algorithm and Mathematics 08
2 Analysis of Algorithm 08
3 Divide and Conquer Algorithm 08
4 Greedy Algorithm 08
5 Dynamic Programming 10
6 Exploring Graphs 10
7 String Matching and NP Completeness 06


Unit No. Topics Teaching Hours
1 Basics of Algorithm and Mathematics
1.1 What is an algorithm?
1.2 Mathematics for Algorithm
1.3 Performance Analysis, Model for Analysis - Random Access Machine (RAM), Primitive Operations
1.4 Time Complexity and Space Complexity
 08
2 Analysis of Algorithm
2.1 The efficiency of algorithm, Best, Average and Worst case Analysis
2.2 Asymptotic Notation
2.3 Solving Recurrence Equation
2.4 Sorting Algorithm
 08
3 Divide & Conquer Algorithm
3.1 Basic of Recursion and its complexity
3.2 The general template for Divide and Conquer Problem
3.3 Problem solving using divide and conquer algorithm – Binary Search, Sorting - Merge Sort and Quick Sort
3.4 Strassen's Matrix Multiplication
08
4 Greedy Algorithm
4.1 General Characteristics of greedy
4.2 Problem solving using Greedy Algorithm: Making change problem
4.3 The Knapsack Problem, Job Scheduling Problem
4.4 Minimum Spanning Trees (Kruskal’s Algorithm, Prim’s Algorithm)
4.5 Dijkstra Algorithm
 08
5 Dynamic Programming
5.1 Introduction, The Principle of Optimality
5.2 Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient
5.3 Making Change Problem, Assembly Line Scheduling
5.4 Knapsack Problem, All pair Shortest Path
5.5 Matrix Chain Multiplication
5.6 Longest Common Subsequence
 10
6 Exploring Graphs and Backtracking
6.1 An introduction to Graph, Basic Definitions
6.2 Traversing Graphs – Depth First Search, Breadth First Search, Topological Sort
6.3 Backtracking – The Eight Queen Problem
6.4 The Knapsack Problem
6.5 Branch and Bound – The Assignment Problem
 10
7 String Matching and NP Completeness
7.1 Introduction
7.2 The naïve string matching algorithm
7.3 The Rabin-Karp algorithm
7.4 Introduction to NP Complete Theory
 06